#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int N = 100100;
struct node {
    int t, x, k;
    int id, d;
} Q[N];

bool cmp ( const node& a, const node& b ) {
    return a.k < b.k || a.k == b.k && a.x < b.x;
}

bool comp ( const node& a, const node& b ) {
    return a.id < b.id;
}

int main() {
    int n, m;
	scanf ( "%d%d", &n, &m );
    for ( int i = 0; i < n; ++i ) {
        scanf ( "%d", &Q[i].t );
        scanf ( "%d", &Q[i].x );
        Q[i].id = i;
    }
    for ( int i = 0; i < n; i += m )
        for ( int j = 0; j < m && j + i < n; ++j )
            Q[i+j].k = i;
    sort ( Q, Q + n, cmp );
	//for(int i = 0; i < n; ++i)
	//	printf("(%d,%d)", Q[i].t, Q[i].x);
	//printf("\n");
    for ( int i = 0, t = 0; i < n; i += m ) {
		for ( int j = i; j < i + m && j < n; ++j )
			t = max( t, Q[j].t );
		//printf("%d\n",t);
        for ( int j = i; j < i + m && j < n; ++j ) {
            if ( j == i || Q[j].x != Q[j - 1].x ) {
                if ( j == i ) t += Q[j].x;
                else t += Q[j].x - Q[j - 1].x;
                int p;
                for ( p = j ; p < n && p < i + m; ++p ){
                    if ( Q[j].x != Q[p].x ) break;
					Q[p].d = t;
				}
                t += 1 + ( p - j ) / 2;
                //while ( --p >= j ) Q[p].d = t;
            }
        }
        if ( i + m < n ) t += Q[i + m - 1].x;
    }
    sort ( Q, Q + n, comp );
    for ( int i = 0; i < n; ++i ) {
        if ( i ) printf ( " " );
        printf ( "%d", Q[i].d );
    }
    printf ( "\n" );
    return 0;
}